\chapter{Připomenutí pojmů}

\begin{definice}
\label{monotonie}
  Nechť $\Sigma$ je abeceda a $\rho$ binární relace na množině $\Sigma^*$.
  Řekneme, že $\rho$ je \emph{monotónní}, pokud pro každé $x_1, x_2, y_1, y_2 \in \Sigma^*$ platí:
  \[x_1 \: \rho \: y_1, \: x_2 \: \rho \: y_2   \Rightarrow x_1 x_2 \: \rho \: y_1 y_2       \]
  Řekneme, že $\rho$ je zprava (zleva) \emph{monotónní}, pokud pro každé $x_1, x_2, y \in \Sigma^*$ platí:
   \[x_1 \: \rho \: x_2,  \Rightarrow x_1 y \: \rho \: x_2 y \;\;\; (y x_1 \: \rho \: y x_2)      \]
  Relace ekvivalence $\sim$ na množine $\Sigma^*$, která je (zprava) monotónní se nazývá (pravá) \emph{kongruence}.
\end{definice}   

Následující věta jinak známá jako Nerodova dává základní algebraickou charakterizaci regulárních jazyků.

\begin{veta}
\label{nerode}
  Nechť $L\subseteq\Sigma^*$. Potom $L$ je regulární právě tehdy, když je sjednocením některých tříd pravé kongruence na $\Sigma^*$ konečného indexu.
\end{veta}

  Abychom na základě předchozího tvrzení mohli o některém jazyku $L$ tvrdit, že je regulární,
  stačí nám nalézt vhodnou kongruenci konečného indexu a ukázat, že daný jazyk je vyplněn nekterými
  třídami ekvivalence. Pokud bychom však chtěli tvrdit opak, tedy že $L$ není regulární, stáli bychom před nelehkým úkolem.
  Museli bychom ukázat, že žádná kongruence požadovaných vlastností neexistuje.  
  Tento problém řeší silnější tvrzení, tzv. Myhillova-Nerodova věta, která se opírá o pojem kontextu.

\begin{definice}
\label{kontext}
  Nechť $L\subseteq\Sigma^*$ je jazyk (ne nutně regulární). Potom pro libovolné $x\in\Sigma^*$ definujme množinu \emph{kontextů} prvku $x$ v jazyce $L$ takto:
  \[C_L(x)=\{(y,z)\mid y,z \in \Sigma^*, yxz \in L\}.\]
Dále definujme pravý a levý kontext (prefix, suffix) následovně:
  \[C_L^r(x)=\{y \in \Sigma^*, xy \in L\},\]
  \[C_L^l(x)=\{y \in \Sigma^*, yx \in L\}.\]
Na základě pravého kontextu můžeme nyní zadefinovat relaci $\sim_L^r$ :
  \[x\sim_L^r y  \Longleftrightarrow C_L^r(x) = C_L^r(y).\]
\end{definice}  

Relaci $\sim_L^r$ se říká \emph{pravá syntaktická ekvivalence} a je zřejmé, že jde o pravou kongruenci.
Relace $\sim_L^r$ má tu vlastnost, že pro libovolný jazyk $L$ platí, že je sjednocením některých
tříd $\Sigma^*/_{\sim_L^r}$. 

\begin{lemma}
Nechť $L\subseteq\Sigma^*$. Potom $L$ je sjednocením některých tříd rozkladu  $\Sigma^*/_{\sim_L^r}$.
\end{lemma}

\begin{proof}
Chceme dokázat, že pro libovolné $x \in \Sigma^*$ patří třída $[x]_{\sim_L^r}$ buď celá do $L$, nebo s ním má prázdný průnik. Nechť tedy $y$ je libovolné slovo takové, že $x\sim_L^r y$. Potom podle definice platí  $C_L^r(x) = C_L^r(y)$, neboli $xz \in L \Longleftrightarrow yz \in L$. Zvolme tedy $z=\epsilon$ a dostaneme $x \in L \Longleftrightarrow y \in L$.
\end{proof}

Další zajímavou vlastností je, že každá pravá kongruence, pro kterou platí, že je jazyk
$L$ sjednocením jejích tříd ekvivalence, je zjemněním relace $\sim_L^r$. Je tedy ze všech takových kongruencí největší.
Tato vlastnost je formálně shrnuta v následujícím lemmatu. 

\begin{lemma}
  Nechť $L\subseteq\Sigma^*$ a $\sim$ je libovolná pravá kongruence na množině $\Sigma^*$ taková, že $L$ je sjednocením některých tříd rozkladu. Potom platí, že $\sim ~\subseteq ~ \sim_L^r$. 
\end{lemma}
\begin{proof}
Dokážeme, že pro libovolná slova $x, y$ taková, že platí $x \sim y$ , platí také $x \sim_L^r y$. Relace $\sim$ je pravá kongruence, a proto platí  $xz \sim yz$ pro libovolné $z \in \Sigma^*$.
Protože $L$ je sjednocením některých tříd ekvivalence  $\sim$, platí $xz \in L \Longleftrightarrow yz \in L$. Tento vztah platí pro libovolné $z$, z toho vyplývá rovnost $C_L^r(x)=C_L^r(y)$ a tedy $x \sim_L^r y$.

\end{proof}

Z Nerodovy věty a předchozího tvrzení už přímo plyne Myhillova-Nerodova věta.
 
\begin{veta}
\label{Myhill-Nerode}
  Nechť $L\subseteq\Sigma^*$. Potom jsou následující tvrzení ekvivalentní:
  \begin{enumerate}
    \item[(i)] L je regulární jazyk.
    \item[(ii)] Relace $\sim_L^r$ má konečný index.
  \end{enumerate}
\end{veta} 



Myhilloval-Nerodova věta je tedy podstatně silnější. Říká nám přesně na kterou
z pravých kongruencí se máme zaměřit. Navíc v případě, že má tato kongruence nekonečný 
index, nemůže být zkoumaný jazyk regulární. 

Předchozí věta nám dává nutnou i postačující
podmínku regularity jazyka a tedy úplnou charakterizaci. Zjistit, zda je
konkrétní jazyk regulární lze však více způsoby. Například sestrojením konečného automatu rozpoznávajícího daný jazyk, nebo pomocí
uzávěrových vlastností. My se zaměříme na některá zobecnění Myhillovyl-Nerodovy věty.

Pro aplikaci Nerodovy věty bylo třeba nalézt pravou kongruenci (monotónní ekvivalenci) konečného indexu. Místo ekvivalence však můžeme uvažovat
obecnější relaci, a to předuspořádání.  

\begin{definice}
  Binární relace $\leq$ na množině $S$ se nazývá \emph{předuspořádání}, právě když je reflexivní a tranzitivní.

  Nechť $X \subseteq S$. Potom říkáme, že množina $X$ je \emph{nahoru uzavřená} vzhledem k $\leq$ ,
  pokud pro libovolné prvky $x \in X$ a $s \in S$ platí:
  \[x \leq s \Longrightarrow s \in X.\]
  Dále budeme nahoru uzavřené množiny nazývat pouze \emph{uzavřené}. 
  
  Relace ekvivalence $\sim$ na $S$ definovaná vztahem
    \[x \: \sim \: y  \Longleftrightarrow x  \: \leq \: y \; \text{a zároveň} \; y  \: \leq \: x      \]
  se nazývá \emph{jádro předuspořádání $\leq$}.   
\end{definice}

Věta \ref{Myhill-Nerode} se nyní přeformuluje do následujícího znění.

\begin{veta}
\label{Myhill-preorder}
  Nechť $L\subseteq\Sigma^*$. Potom $L$ je regulární právě tehdy, když je uzavřený vzhledem k nějakému 
  monotónnímu předuspořánaní množiny $\Sigma^*$, jehož jádro má konečný index.
\end{veta}

Jak je vidět, přechodem k předuspořádání jsme se nikam významně neposunuli. Věta se totiž stále odvolává na ekvivalenci konečného indexu.
Platí totiž, že je-li jazyk $L$ uzavřený vzhledem k monotónnímu předuspořádání $\leq$, jehož jádro má konečný index,
pak je $L$ sjednocením některých tříd jádra $\leq$. Věta \ref{Myhill-preorder} je tedy pouze přeformulovaná věta  \ref{Myhill-Nerode}.
Tento postup byl původně použit z jiných důvodů, monónní předuspořádání dávájí totiž jenmější klasifikaci regulárních jazyků.
Zajimavé je však zamyšlení, jestli nelze rozpoznávat regulární jazyky i předuspořádáními nekonečných indexů.
Hledaným zobecněním jsou dobrá předuspořádání, kterým se bude věnovat následující kapitola.













\shorthandon{-} 
